剑指Offer 40 数组中只出现一次的数字

题目描述

一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。

思路

这不是一道正常题，因为他的考点就是异或运算；我刚开始还在想先排个序，然后每次移动两位；这样就可以比较出来了；然而时间复杂度O（n）可以接受，空间复杂度O（1）是什么鬼？除了异或运算应该不可能做到的吧；

讲讲异或运算，相同的数字亦或运算后就是零；1^0=0^1 = 1;0^0=1^1=0;
所以我们就获得了重要情报，一群出现两次的数和一个只出现一次的数进行异或运算就是这个只出现一次的；
那么两个怎么办呢？首先对全部进行异或运算，得到的肯定不是0，因为有两个不一样嘛，这个数中二进制1的位置，表现了两个只出现一次的数的不同，然后我们就可以据此分类；

代码

public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) {
    if (array==null||array.length<2)            //用例检查
        return;
    int allxor=0;                               //用于全部异或
    for (int i = 0; i < array.length; i++) {        
        allxor^= array[i];
    }
    int flag = 1;               
    while ((allxor & flag)==0)                  //找的这么一个特征值
        flag <<= 1;                             //移动1的位置
    for (int i = 0; i < array.length; i++) {    //通过特征值分组
        if ((array[i]&flag)==0)
            num1[0] ^= array[i];
        else
            num2[0] ^= array[i];
    }
}

收获

异或运算真是太强大了；
java在位运算上总感觉没有C那么自然；

2017-04-02